import sys

# main_num = int(input())
# num_list = [int(i) for i in input().split()]

main_num = 28
num_list = tuple([int(i) for i in '1507 6611 20966 571 1023 9390 16632 16742 12152 18621 4670 25368 15333 7461 12737 24979 10819 1505 13802 20395 6112 18161 23373 9154 14116 24391 27280 27686'.split()])


def is_prime(n):
    if n == 1:
        return 1
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
           return 0
    return 1

jishu = []
oushu = []
for i in num_list:
    if i % 2 == 0:
        oushu.append(i)
    else:
        jishu.append(i)

def main():
    prime_list = []
    if not oushu or not jishu:
        return 0
    for i in range(len(oushu)):
        for j in  range(len(jishu)):
            if is_prime(oushu[i] + jishu[i]):
                prime_list.append((i, j+len(oushu)))
    i = 1
    while True:
        i += 1
        if not digui(tuple(prime_list), i):
            return i - 1
        print(i)

cache = {}
def digui(next_list, num):
    if next_list in cache and num <= cache[next_list]:
        return True
    if len(next_list) < num:
        return False
    x_list = set()
    y_list = set()
    print(next_list, num)
    if num == 0:
        return True
    if digui(next_list[1:], num):
        return True
    _next_list = []
    for i in next_list[1:]:
        if i[0] in next_list[0] or i[1] in next_list[0]:
            continue
        _next_list.append(i)
    _next_list = tuple(_next_list)
    if digui(_next_list, num -1):
        cache[_next_list]
        = num -1
        return True
    else:

    return False


main()


